COMMENT ⊗   VALID 00007 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	ideas[w82,jmc]		string search
C00005 00003	Jan 27	eco-rumor
C00006 00004	Jan 27 - Partial reflection principle
C00007 00005	Feb 7 - Group representation theory
C00008 00006	Feb 7 - Parallel matrix multiplication my require size dependent routines
C00009 00007	Feb 7 - Proposal for treachery
C00010 ENDMK
C⊗;
ideas[w82,jmc]		string search

∂23-Jan-82  2316	JMC  	improved string search  
To:   cl.boyer at UTEXAS-20, cl.moore at UTEXAS-20   
Here is an "improvement" on your string search whose correctness statement
might be difficult to formalize.  The algorithm is essentially that given
in your book, except for a change in the initialization to avoid updating
the table for all letters of the alphabet.  Each entry in the table includes
your (DELTA1 K) in its low order bits and an integer <search number> in its
high order bits.  When we start a new search, we update the entries
corresponding to the letters in the pattern string but with a search number
one larger than that of the last search.  We don't bother changing the
entries for letters that don't appear in the pattern string, because a
simple comparison when the letter is encountered in the text shows that
the entry is obsolete.  Only when the search number threatens to overflow
the allocated field do we go through the entire table and restart with
search number 1.

Since I don't know the literature and couldn't find a reference to this
kind of searching in Knuth vols. 1-3, this may be an old idea.

Notice that stating the correctness and the efficiency of the algorithm
requires taking into account that the algorithm may be used many times.

Jan 27	eco-rumor
	The California condor is dying out because it requires human carrion.

Jan 27 - Partial reflection principle
	Carolyn points out the existence of partial reflection principles
and partial self confidence principles.  true(n,p) ≡ p for expressions
p of quantifier depth ≤ n.  An analogous scheme would get around
Montague's paradoxes of knowledge.

Feb 7 - Group representation theory
	Mappings into some other entities than linear groups might get
around the problem that non-commutative non-compact groups require
infinite dimensional representations for completeness.  Mappings into
and out of the groups need to be inter-related.

Feb 7 - Parallel matrix multiplication my require size dependent routines
	The ideas in my MULTIP[1,JMC]@S1 are probably not adequate
for programming subroutines.  Consider a matrix multiplication
subroutine.  Which parts are done in parallel and how much
parallelism is allowed needs to depend on the size of the matrices
in a more flexible way than I have allowed.

Feb 7 - Proposal for treachery
	A modest proposal for treachery.  We give the Chinese communists
Taiwan which gets them doubling their foreign trade, nuclear reactors,
a shipbuilding industry, etc.  They can try to control it by exchanging
populations.  The social scientists get to study whether they can
maintain its productivity.  They conquer Indochina for us.